package com.tgy.algorithm.base._滑动窗口;

import java.util.LinkedList;

/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，
 * 必须满足sub中最大值-sub中最小值<=num,返回arr中达标子数组的数量
 */
public class _数组中子数组最大值与最小值差距的数量 {


    public static int getSubArr(int[] nums,int distance) {

        if (nums == null || nums.length == 0 || distance < 0) {
            return 0;
        }

        LinkedList<Integer> minQueue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();

        int len = nums.length;
        int total = 0;
        int leftIndex = 0;
        for (int i = 0; i < len; i++) {
            int value = nums[i];
            while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] <= value) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(i);

            while (!minQueue.isEmpty() && nums[minQueue.peekLast()] >= value) {
                minQueue.pollLast();
            }
            minQueue.offerLast(i);


            while (true) {
                // TODO ..
                if (nums[maxQueue.peekFirst()]  - nums[minQueue.peekFirst()] > distance) {
                    total += (i - leftIndex);
                }else {
                    break;
                }

                if (minQueue.peekFirst() == leftIndex) {
                    minQueue.pollFirst();
                }
                if (maxQueue.peekFirst() == leftIndex) {
                    maxQueue.pollFirst();
                }
                leftIndex++;
            }

        }

        while (leftIndex < len) {
            total += (len - leftIndex);
            leftIndex++;
        }

        return total;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,4,6,1,2,3};
        int count = getSubArr(nums, 2);
        System.out.println(count);
    }
}
